package 华为OD机试真题2023.进阶题;

import utils.MyUtil;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.*;

public class HJ08_基站维修工程师 {
    public static void main(String[] args) throws FileNotFoundException {
        MyUtil.START();
        Solution();
        //        Solution2();
        //        Solution3();
        MyUtil.END();
    }

    static int[] visited2 = new int[10];
    static int tmp, minDist = Integer.MAX_VALUE;
    static LinkedList<Integer> tmpPath = new LinkedList<>();
    static LinkedList<Integer> path = new LinkedList<>();

    static void Solution() throws FileNotFoundException {
        Scanner in = new Scanner(new File("src/main/java/华为OD机试真题2023/进阶题/input/08.txt"));
        int N = in.nextInt();
        int[][] matrix = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                matrix[i][j] = in.nextInt();
            }
        }
        dfs(matrix, 0, 0);
        System.out.println(path);
        System.out.println(minDist);
    }

    static void dfs(int[][] matrix, int index, int count) {
        int len = matrix[0].length;
        if (count == len) {
            if (index == 0) {
                if (tmp < minDist) {
                    path.clear();
                    path.addAll(tmpPath); // 注意这里不能直接 path=tmpPath 这是引用拷贝 会导致 原来path对象丢失。要用浅拷贝。
                    minDist = tmp;
                }
            }
            return;
        } else if (count != 0 && index == 0) {
            return;
        }
        for (int i = 0; i < len; i++) {
            int tmpDist = matrix[index][i];
            if (tmpDist > 0 && visited2[i] == 0) {
                visited2[i] = 1;
                tmp += tmpDist;
                tmpPath.addLast(i + 1);
                dfs(matrix, i, count + 1);
                tmpPath.removeLast();
                tmp -= tmpDist;
                visited2[i] = 0;
            }
        }
    }

    static void Solution2() throws FileNotFoundException {
        Scanner in = new Scanner(new File("src/main/java/华为OD机试真题2023/进阶题/input/08.txt"));
        int num = in.nextInt();
        if (num <= 1) {
            System.out.println(0);
        }
        int[][] arr = new int[num][num];
        for (int i = 0; i < num; i++) {
            for (int j = 0; j < num; j++) {
                arr[i][j] = in.nextInt();
            }
        }
        boolean visited[] = new boolean[num];
        int min = Integer.MAX_VALUE;
        for (int i = 1; i < num; i++) {
            visited[i] = true;
            tmpPath.addLast(i + 1);
            int temp = dfs1(arr, visited, i, arr[0][i]);
            visited[i] = false;
            min = Math.min(temp, min);
            tmpPath.removeLast();
        }
        System.out.println(min);
    }

    static int dfs1(int[][] arr, boolean[] visited, int curIndex, int len) {
        visited[curIndex] = true;
        if (judge(visited)) {
            visited[curIndex] = false;
            return len + arr[curIndex][0];
        }
        int min = Integer.MAX_VALUE;
        for (int i = 1; i <= arr.length - 1; i++) {
            if (visited[i]) {
                continue;
            }
            tmpPath.addLast(i + 1);
            int temp = dfs1(arr, visited, i, len + arr[curIndex][i]);
            if (temp < min) {
                min = temp;
                System.out.println(tmpPath);
            }
            //            min = Math.min(temp, min);
            tmpPath.removeLast();
        }
        visited[curIndex] = false;
        return min;
    }

    // 判断是否除0外，其余站点都已经经过
    static boolean judge(boolean[] visited) {
        for (int i = 1; i < visited.length; i++) {
            if (!visited[i]) {
                return false;
            }
        }
        return true;
    }

    static int min = Integer.MAX_VALUE;

    static void Solution3() throws FileNotFoundException {
        Scanner sc = new Scanner(new File("src/main/java/华为OD机试真题2023/进阶题/input/08.txt"));
        int n = sc.nextInt();
        sc.nextLine();
        int[][] distance = new int[n][n]; // 路程转化为二维数组
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                distance[i][j] = sc.nextInt();
            }
        }

        for (int i = 1; i < distance.length; i++) {
            List<Integer> stepList = new ArrayList<>();
            stepList.add(i); // 从基站2开始走
            handle(distance, i, stepList, distance[0][i]);
        }
        System.out.println(min);
    }

    static void handle(int[][] ints, int index, List<Integer> step, int sum) {

        if (step.size() + 1 == ints.length) { // 走完所有的基站，准备返回基站1
            min = Math.min(min, sum + ints[index][0]); // 记得加上基站1的路程
        } else {
            for (int i = 1; i < ints.length; i++) {
                if (step.contains(i)) { // 已经走过的基站不需要再走
                    continue;
                }
                step.add(i); // 走过的基站
                handle(ints, i, step, sum + ints[index][i]); // index到达的基站，i下次去的基站
                step.remove(step.size() - 1); // 刚走过的基站需要剔除以便进行下一个循环
            }
        }
    }
}
